package com.cruelbb.wonderful2025.algo.sort;

public class QuickSort {

    public static int partition(int[] array, int left, int right) {
        int base = array[left];
        int i = left, j = right;
        while (i < j) {
            while (i < j && array[j] >= base)
                j--;
            while (i < j && array[i] <= base)
                i++;
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
        array[left] = array[i];
        array[i] = base;
        return i;
    }

    public static void quickSort(int[] array, int left, int right) {
        if (left >= right) {
            return;
        }
        int pivot = partition(array, left, right);
        quickSort(array, left, pivot - 1);
        quickSort(array, pivot + 1, right);
    }
}
